Communication and computer networks consist of a variety of hardware equipment and software and are increasing in use and complexity. The popularity of computer networks as a computer paradigm and the growth in amount of data transferred between network users has forced the capacity of networks and protocols to increase with time. A variety of network communication protocols transfer data between devices coupled by a network. Ethernet and Asynchronous Transfer Mode are examples of such communication protocols.
Asynchronous Transfer Mode ("ATM", hereafter) provides bandwidths as low as 25 megabits/second using twisted cables and as high as 10 gigabits/second using optical cables. An ATM switch transfers cells between various points in a network. A cell contains control information, a header, and a data packet. The header within the cell contains switching identifiers enabling the ATM switch to route the data. The ATM switch interrogates each switching identifier it receives against a programmed list to determine which output channel the cell should be output. When the data packets are received by the intermediate node, destination information is contained in header which accompanies the data packet. The node determines whether it has previously agreed to route the data packets for that transmission by examining its memory to determine whether the destination information has previously been stored. If it has, a forwarding address has also been stored and the node forwards the data packet to the next node in the route toward the destination address. As it receives each data transmission, the node interrogates the contents of its memory to determine if it has agreed to forward the transmission. If the destination information is present, the memory produces a forwarding address associated with the destination information for routing the data packet to the next node.
Content addressable memories ("CAM", hereafter) store the switching identifiers for the ATM switch. In an associative or content addressable memory, match words and switching identifiers are stored in associated pairs in memory. When the CAM receives a reference word it determines whether a match word equal to the reference word is stored in memory. If so, it produces the link word associated with the matched reference word. An important aspect of a CAM is the association between the match word and its associated link word, much like a dictionary, where each word is stored in association with its definition. In a dictionary, a provided word is looked up and the definition associated with the word is produced. In a CAM, a provided reference word is looked up, i.e., compared with a match word and, if they are equal, a link word associated with the match word is produced.
In general, the memory array of an ATM CAM is organized into a match word table and a link word table. If a reference word matches an entry from a match word table the associated link word is produced at the output. If no match is found, the output word indicates the failure by, for example, setting an error flag bit. In an ATM application, the reference word consists of switching identifiers. The switching identifiers consist of a virtual path identifier ("VPI", hereafter) and a virtual channel identifier ("VCI", hereafter). The CAM compares the VPI and VCI in the header with the VPI and VCI entries in the CAM. The switching identifiers determine if a virtual path connection ("VPC", hereafter) exists or a virtual circuit connection ("VCC", hereafter) exists.
Smaller sized CAMs often provide this function in hardware such that the reference word is simultaneously compared with every word in the match word table, thereby operating in a full parallel mode in which the output word is produced in one clock cycle. However, as the need for larger CAMs grows, the parallel mode is not possible due to longer search times.
A previously known technique for implementing a large CAM is to presort the memory into distinct classes. For example, a 4,096 word deep CAM is preclassified into four separate, shallower 1,024 word CAMs wherein particular match and link word pairs could only be stored in one of the CAMs. However, this approach has a disadvantage in that the CAM corresponding to one of the classes could be filled while others had substantial vacancies, thereby effectively reducing the depth of the CAM. Adding logic to the CAM for dynamically adjusting the size of each CAM as needed would substantially increase the complexity and cost of the CAM.
Furthermore, in order to establish a VCC or VPC, two searches to each CAM entry are required, whether a parallel or serial search strategy is used. The first search checks for a VCC, comparing the input header and the switching identifiers. The second search is for the VPC, comparing the input header and the switching identifiers.
Two known approaches are used to perform parallel searches. One method uses one CAM array, interrogating each entry twice. Another method uses two separate CAMs, with each CAM only storing either VCI or VPI. The one CAM approach will take more time than the dual CAM approach. However, the dual CAM approach adds more hardware and cost to a switch network.